function DublyLinkedList() {

    this.head = null
    this.tail = null
    this.length = 0

    function Node(data) {
        this.next = null
        this.prev = null
        this.data = data
    }

    DublyLinkedList.prototype.toString = function () {
        let currentNode = this.head
        let resultString = ''
        while (currentNode) {
            resultString += ',' + currentNode.data
            currentNode = currentNode.next
        }
        return resultString.replace(',', '')

    }

    DublyLinkedList.prototype.append = function (element) {
        let newNode = new Node(element)
        if (this.length == 0) {
            this.head = newNode
            this.tail = newNode
        } else {
            this.tail.next = newNode
            newNode.prev = this.tail
            this.tail = newNode
        }
        this.length++
    }

    DublyLinkedList.prototype.getPositiveIndex = function (index) {
        if (index >= this.length || index < -this.length) {
            throw (`the index is not illegal `)
        }
        return index >= 0 ? index : index + this.length
    }

    DublyLinkedList.prototype.getNode = function (index = 0) {
        let idx = this.getPositiveIndex(index)
        let currentNode;
        if (idx < Math.ceil(this.length / 2)) {
            currentNode = this.head
            console.log('from head')
            for (let i = 0; i < idx; i++) {
                currentNode = currentNode.next
            }
        } else {
            currentNode = this.tail
            console.log('from tail')
            for (let i = this.length - 1; i > idx; i--) {
                currentNode = currentNode.prev
            }
        }
        return currentNode
    }

    DublyLinkedList.prototype.get = function (index) {
        return this.getNode(index).data
    }

    DublyLinkedList.prototype.indexOf = function (element) {
        let i = 0;
        let currentNode = this.head
        while (i < this.length) {
            if (currentNode.data == element) {
                return i
            }
            currentNode = currentNode.next
            i++
        }
        return -1
    }

    DublyLinkedList.prototype.insert = function (index, element) {
        let currentNode = this.getNode(index)
        let newNode = new Node(element)
        newNode.next = currentNode
        currentNode.prev = newNode
        if (idx == 0) {
            this.head = newNode
        } else {
            let prevNode = currentNode.prev
            prevNode.next = newNode
            newNode.prev = prevNode
        }
        this.length++
    }

    DublyLinkedList.prototype.update = function (index, element) {
        let currentNode = this.getNode(index)
        currentNode.data = element
    }

    DublyLinkedList.prototype.removeAt = function (index) {
        let currentNode = this.getNode(index)
        let prevNode = currentNode.prev
        let nextNode = currentNode.next
        if (this.length == 1) {
            //如果只有一个节点
            this.head = null
            this.tail = null
        } else {
            if (!prevNode) {
                //如果是头节点
                this.head = nextNode
                nextNode.prev = null
                currentNode.next = null
            }else if (!nextNode) {
                //如果是尾节点
                this.tail = prevNode
                prevNode.next = null
                currentNode.prev = null
            }else{
                prevNode.next = nextNode
                nextNode.prev = prevNode
            }
        }
        this.length--
    }
    
    DublyLinkedList.prototype.remove = function(element){
        let currentNode = this.head
        let removeNode
        while(currentNode){
            if(currentNode.data == element){
                removeNode = currentNode
                break
            }
            currentNode = currentNode.next
        }
        if(!removeNode) return
        removeNode.prev.next = removeNode.next
        removeNode.next.prev = removeNode.prev
        this.length--
    }

    DublyLinkedList.prototype.isEmpty = function(){
        return this.length == 0
    }

    DublyLinkedList.prototype.size = function(){
        return this.length
    }

    DublyLinkedList.prototype.forwardString = function(){
        let currentNode = this.head
        let result = ''
        while(currentNode){
            result += currentNode.data + ','
            currentNode = currentNode.next
        }
        return result
    }

    DublyLinkedList.prototype.backwardString = function(){
        let currentNode = this.tail
        let result = ''
        while(currentNode){
            result += currentNode.data + ','
            currentNode = currentNode.prev
        }
        return result
    }
}

let dl = new DublyLinkedList()
dl.append('a')
dl.append('b')
dl.append('c')
dl.append('d')
dl.append('e')
console.log(dl.toString())
console.log(dl.indexOf('c'))
